19.4 KB · ⇊ 12 parts · ⤓ Micron 19.4 KB · ⤓ HTML 37.7 KB

top

En informatique et en logique, un système formel est dit complet au sens de Turing ou Turing-complet (par calque de l’anglais Turing-completecite-ref-1[1]) s’il possède un pouvoir expressif au moins équivalent à celui des machines de Turing. Dans un tel système, il est donc possible de programmer n'importe quelle machine de Turing.

Cette notion est rendue pertinente par la thèse de Church, qui postule l’existence d’une notion naturelle de calculabilité. Ainsi, le pouvoir expressif des machines de Turing coïncide avec celui des fonctions récursives, du lambda calcul, ou encore des machines à compteurs.

Bien que certains modèles de calcul, appelés des hypercalculs, soient strictement plus expressifs que les machines de Turing, ces modèles sont des objets de spéculation (requérant par exemple d’effectuer une infinité d’opérations, ou de calculer sur l’ensemble des nombres réels) et l’on ignore s’ils sont physiquement réalisables.

Dans ces conditions, la thèse de Church conjecture l’universalité du modèle de calcul des machines de Turing : tout système Turing-complet serait en fait équivalent aux machines de Turing.

• Langages de programmation Turing-complets

• Langages qui ne sont pas Turing-complets

• Exemples en dehors des langages de programmation

• Articles connexes

• Notes et références

• Notes

• Références

• Annexes

• Articles connexes

De même qu'un modèle de calcul, un langage informatique est dit Turing-complet s'il permet de représenter toutes les fonctions calculables au sens de Turing et Church (nonobstant la finitude de la mémoire des ordinateurscite-ref-2[note 1]).

Certains auteurs prennent cette propriété pour définition d’un langage de programmationcite-ref-3[2]cite-ref-4[3], mais d'autres définitions peuvent être choisiescite-ref-5[4].

Les langages de programmation usuels (C, Java…) sont Turing-complets car ils possèdent tous les ingrédients nécessaires à la simulation d'une machine de Turing universelle (compter, comparer, lire, écrire, etc.)cite-ref-6[5]. Le langage C++ est également Turing-complet, et le sous-ensemble permettant la programmation générique (templates) l'est aussi[réf. nécessaire].

Le langage SQL, à l'origine non complet au sens de Turing, l'est devenu avec la norme SQL:1999 lui permettant d'écrire des requêtes récursives[réf. nécessaire].

Le langage LaTeX (issu du TeX), destiné à la composition de documents, est également Turing-completcite-ref-7[6].

Le langage HTML seul n'est pas Turing-complet, cependant il a été prouvé que le langage CSS (en version 3) permet de construire l'automate cellulaire élémentaire de code 110 (voir Rule 110 (en)cite-ref-8[7]), connu pour être universel au sens de Turing. Ces deux langages étant souvent indissociables, on peut conclure que le HTML+CSS est Turing-complet, et cette association en fait donc théoriquement un langage de programmation.

Un langage Turing-complet hérite des caractéristiques d'une machine de Turing. Par exemple, le problème de l'arrêt est indécidable, donc il est impossible d'écrire un programme qui dit si un programme arbitraire qu'on lui fournit se termine ou non.

Certains langages dédiés au traitement de problèmes spécifiques ne sont pas Turing-complets. Système F, un formalisme de lambda calcul en est un exemple. Par ailleurs — par conception —, les langages totaux (en), où tous les calculs se terminent nécessairement (comme le langage Gallina de l'assistant de preuve Rocq), ne sont pas non plus Turing-complets. Cependant, ces derniers sont en pratique capables de calculer tout ce qui est intéressantcite-ref-9[8]cite-ref-10[9], en d'autres termes ils peuvent mettre en œuvre toutes les fonctions dont nous pourrions avoir besoin dans la vie pratique ; les calculs qui leur échappent, soit ont une complexité au-delà de l'imaginable et du réalisable, soit ne se terminent pas. La compilation doit alors démontrer la terminaison des programmes, ou nécessiter une interaction avec le programmeur pour certaines démonstrations, mais c'est le prix à payer pour une qualité de code qui est correcte par construction.

Certains jeux et logiciels présentent une complétude de Turing de manière fortuite, sans que leurs concepteurs l'aient intentionnellement recherchée ou anticipée.

• Dwarf Fortresscite-ref-themarysue-11-0[10]

• Magic : L'Assembléecite-ref-12[11]

• Cities: Skylinescite-ref-13[12]

• Démineur avec grille infiniecite-ref-14[13]

• Le jeu de la vie, un automate cellulairecite-ref-15[14]

• PowerPointcite-ref-16[15]

• Habbocite-ref-17[16]

• Baba Is Youcite-ref-18[17]

• Microsoft Excelcite-ref-19[18]

• Opus Magnumcite-ref-20[19]

Dans certains cas, l'intégration d'une propriété de complétude de Turing est intentionnelle, en raison de la capacité à implémenter des portes logiques et à contrôler un circuit électrique, constituant ainsi une composante essentielle du jeu :

• Minecraftcite-ref-21[20]

• Factoriocite-ref-22[21]

• Boucle infinie

• Théorème de Rice

• Théorie de la Calculabilité

• Thèse de Church

cite-note-2note 1. ↑ Un ordinateur a une mémoire finie, le modèle de calcul des machines de Turing a une mémoire illimitée.

cite-note-11. ↑ bureau-de-la-traduction2017Bureau de la traduction, fiche de la banque de données TERMIUM Plus, sur termiumplus.gc.ca, 2 février 2017 (consulté le 23 mai 2019)

cite-note-32. ↑ mitchell2003john-c-mitchell2003(en) John C. Mitchell, Concepts in Programming Languages, Cambridge University Press, 2003 (lire en ligne), p. 14 : « The fact that all standard programming languages express precisely the class of partial recursive functions is often summarized by the statement that all programming languages are Turing complete. »

cite-note-43. ↑ maclennan1999bruce-j-maclennan1999(en) Bruce J. MacLennan, Principles of Programming Languages, Oxford University Press, 1999, Introduction: What is a programming language? : « A programming language is a language that is intended for the expression of computer programs and that is capable of expressing any computer program. This is not a vague notion. There is a precise theorical way of determining whether a computer language can be used to express any program, namely, by showing that it is equivalent to a universal Turing machine. »

cite-note-54. ↑ (en) « Are non Turing-complete languages considered programming languages at all? », sur Stack Exchange À la question posée, une réponse sélectionnée considère que la Turing-complétude n’est pas requise pour considérer un langage comme langage de programmation..

cite-note-65. ↑ Exemple de mise en œuvre d'une machine de Turing en C : pablo-rinaldi-juampi-2014juan-pablo-rinaldi-juampi-2014(en) Juan Pablo Rinaldi (juampi), « An implementation of a Turing Machine in C », sur GitHub, 13 janvier 2014 (consulté le 21 mai 2019).

cite-note-76. ↑ « LaTeX is More Powerful than you Think - Computing the Fibonacci Numbers and Turing Completeness - ShareLaTeX, Éditeur LaTeX en ligne », sur fr.sharelatex.com (consulté le 2 juin 2017).

cite-note-87. ↑ jonaseli-jonas(en) Eli & Jonas, « CSS3 proven to be "Turing-complete" », sur Accodeing to you (consulté le 17 mai 2019).

cite-note-98. ↑ « On the importance of Turing completeness », sur Lambda the Ultimate (en).

cite-note-109. ↑ werner1997benjamin-werner1997Benjamin Werner, « Sets in Types, Types in Sets », Proceedings of TACS'97,‎ 1997.

cite-note-themarysue-1110. ↑ Andrew Cedotal, « Man Uses World's Most Difficult Computer Game to Create … A Working Turing Machine », sur www.themarysue.com, 16 avril 2010 (version du 27 juin 2015 sur Internet Archive).

cite-note-1211. ↑ (en) Alex Churchill, « Magic: The Gathering is Turing Complete », sur Cornell University, 23 avril 2019 (version du 7 mai 2019 sur Internet Archive).

cite-note-1312. ↑ bali2019daniel-bali2019(en) Daniel Bali, « Cities: Skylines is Turing Complete », sur Medium, 15 juillet 2019 (consulté le 15 octobre 2025)

cite-note-1413. ↑ kaye2000richard-kaye2000Richard Kaye, « Minesweeper is NP-complete », The Mathematical Intelligencer, vol. 22, no 2,‎ mars 2000, p. 9–15 (ISSN 0343-6993, DOI 10.1007/bf03025367, lire en ligne, consulté le 17 septembre 2025)

cite-note-1514. ↑ Paul Rendell, « A Turing Machine in Conway's Game of Life », sur rendell-attic.org, 12 janvier 2005 (version du 8 juillet 2009 sur Internet Archive).

cite-note-1615. ↑ wildenhain2017tom-wildenhain2017(en) Tom Wildenhain, « On the Turing Completeness of MS Powerpoint »(Archive.org • Wikiwix • Archive.is • Google • Que faire ?), sur andrew.cmu.edu, 16 mars 2017 (consulté le 10 juillet 2020).

cite-note-1716. ↑ habbo-2020habbo-habbo-2020(en) Habbo (@Habbo), « We know that there are some talented Habbos out there but this one might just take the cake! One of our players @sirjonasxx took on the challenge of creating a functioning Turing machine in-game and they SUCCEEDED! Let’s check it out. », sur Twitter, 9 novembre 2020 (consulté le 30 novembre 2020)

cite-note-1817. ↑ « TwitLonger — When you talk too much for Twitter », sur twitlonger.com (consulté le 28 novembre 2021).

cite-note-1918. ↑ 2024« Chapter 1: Formulas in Excel », dans Microsoft Excel Functions and Formulas, De Gruyter, 11 mars 2024, 1–36 p. (ISBN 978-1-68392-852-2, lire en ligne)

cite-note-2019. ↑ caldwell2017brendan-caldwell2017(en) Brendan Caldwell, « Opus Magnum player makes an alchemical computer », Rock, Paper, Shotgun,‎ 20 novembre 2017 (lire en ligne, consulté le 17 septembre 2025)

cite-note-2120. ↑ gunivers2019(en) Gunivers, « Data Pack - Universal Turing Machine », sur YouTube, 17 juillet 2019 (consulté le 6 mai 2020).

cite-note-2221. ↑ 1432019iquick-1432019 [vidéo] « Factorio turing machine with No Combinators », IQuick 143, 2 janvier 2019, 6:48 min (consulté le 30 mai 2025)

• Alan Turing

• Thèse de Church

• Portail de l'informatique théorique

• Portail de la logique